#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>


#include "../include/digraph.h"
#include "../include/queue.h"

typedef struct nodeCDT * nodeADT;
typedef struct edgeCDT * edgeADT;
	
typedef struct nodeCDT
{
	nodeT info;
	int tag;
	int iedges;			/* cantidad de aristas que llegan a este nodo */
	edgeADT adyac; 		/* lista de adyacencia*/
	nodeADT next; 		/* siguiente en la lista de nodos */
	edgeADT	actual;		/* sirve para iterar por la lista de adyacencias */
}nodeCDT;

typedef struct edgeCDT
{
	edgeT info;
	nodeADT adyac;		/*nodo al que apunta la adyacencia (puntero al nodo)*/
	edgeADT nextEdge;	/*siguiente en la lista de adyacencia (a la siguiente arista)*/
}edgeCDT;


struct digraphCDT 
{
	nodeADT nodes;			/*lista de nodos*/
	nodeADT actual;
	int NodeCount;
	int EdgeCount;
	int nsize;
	int esize;				/* tamaños de la info del nodo y de la arista */
	CmpNodesFn cmpFn;
	queueADT queue;
};

static void UnMark(digraphADT digraph);
static void FreeForAll(digraphADT, nodeADT nodes);
static void FreeNode(digraphADT digraph, nodeADT node);
static void FreeEdge(digraphADT digraph, edgeADT edge);
static int InsertEdge(digraphADT digraph, nodeADT nodeSrc, nodeADT nodeTgt, edgeT edge);
static nodeADT SearchNode(digraphADT digraph, nodeT info);
static int PathBFS(digraphADT digraph, nodeADT begin);

/* FUNCIONES ESTATICAS */

static void 
UnMark(digraphADT digraph)
{
	nodeADT naux;
	
	naux = digraph -> nodes;
	
	while(naux != NULL)
	{
		naux -> tag = 0;
		naux = naux -> next;
	}
	
	return;
}

static void 
FreeForAll(digraphADT digraph, nodeADT nodes)
{
	if (nodes == NULL)
		return;
		
	FreeForAll(digraph, nodes -> next);	/* llamada recursiva en la lista de nodos, al volver hacia atras libera */
	FreeNode(digraph, nodes);	/* libera el nodo con todas sus adyacencias */
	return;
}
static void 
FreeNode(digraphADT digraph, nodeADT node)
{
	edgeADT curr, follow;
	
	curr = follow = node -> adyac;

	/* Destruye todas las aristas que estan asociadas al nodo a destruir */
	
	while (follow != NULL)
	{
		curr = follow;
		follow = follow -> nextEdge;
		FreeEdge(digraph, curr);
		digraph -> EdgeCount--;
	}
	
	free(node -> info);
	free(node);
	return;
}

static void
FreeEdge(digraphADT digraph, edgeADT edge)
{
	free(edge -> info);
	free(edge);
	return;
}

static int 
InsertEdge(digraphADT digraph, nodeADT nodeSrc, nodeADT nodeTgt, edgeT edge)
{
	edgeADT prev, rec;
	edgeADT aux = NULL;
		
	prev = rec = nodeSrc -> adyac;
	
	while (rec != NULL && digraph -> cmpFn(rec -> adyac -> info, nodeTgt -> info) < 0)
	{
		prev = rec;
		rec = rec -> nextEdge;
	}
	
	/* Si la arista ya existia, se sobreescribe la informacion de la arista con la nueva */
	
	if (rec != NULL && digraph -> cmpFn(rec -> adyac -> info, nodeTgt -> info) == 0)
	{	
		if ( memcpy(rec -> info, edge, digraph -> esize) == NULL)
		{
			fprintf(stderr, "CreateEdge: Couldn't update edge data \n");
			return 0;
		}

		return 1;
	}
	
	/* Si no existe, se crea */
	
	if ( (aux = calloc(1, sizeof(struct edgeCDT))) == NULL )
	{
		fprintf(stderr, "CreateEdge: Not enought memory to create Edge \n");
		return 0;
	}
	
	/* aloca el espacio para almacenar el dato del arco */
	
	if ( (aux -> info = malloc(digraph -> esize)) == NULL)
	{
		fprintf(stderr, "CreateEdge: Not enought memory to save edge info \n");
		free(aux);
		return 0;
	}
	
	/* copia el dato en la arista */
	
	if (memcpy(aux -> info, edge, digraph -> esize) == NULL)
	{
		fprintf(stderr, "CreateEdge: Unable to copy edge data to the newly created edge \n");
		free(aux -> info);
		free(aux);
		return 0;
	}
	
	aux -> nextEdge = rec;	/* siguiente en la lista de adyacencias */
	aux -> adyac = nodeTgt; /* nodo al que apunta la arista */
	
	if (prev == rec)
		nodeSrc -> adyac = aux;	/* aux es el primer arco en la lista de adyacencias */
	else
		prev -> nextEdge = aux; /* si no es el primero, quedó entre medio de 2 nodos o al final */
	
	digraph -> EdgeCount++;
	return 1;
}

static nodeADT
SearchNode(digraphADT digraph, nodeT info)
{
	nodeADT aux;
	
	aux = digraph -> nodes;
	 
	while (aux != NULL && digraph -> cmpFn(aux -> info, info) != 0)
		aux = aux -> next;
	
	if (aux == NULL)
		return NULL;
	
	return aux;
}

static int 
PathBFS(digraphADT digraph, nodeADT begin)
{
	/* no se chequean los argumentos, pues la única función que utiliza PathBFS, lo hace de antemano */
	
	queueADT q;
	edgeADT eaux;
	nodeADT naux;
	
	UnMark(digraph);  /* antes de recorrer el digrafo, se desmarca o el recorrido será erroneo */
	
	if ( (q = NewQueue()) == NULL)
	{
		fprintf(stderr, "SetIteratorBFS: Unable to initialize iterator \n");
		return 0;
	}

	Enqueue(digraph -> queue, begin -> info);
	begin -> tag = 1;
	
	Enqueue(q, begin);
	
	while(!QueueIsEmpty(q))
	{
		
		naux = Dequeue( q );
		eaux = naux -> adyac;
		
		while(eaux != NULL)
		{
			if (!eaux -> adyac -> tag)
			{	
				Enqueue(digraph -> queue, eaux -> adyac -> info);
				eaux -> adyac -> tag = 1;
				Enqueue(q, eaux -> adyac);
			}
			
			eaux = eaux -> nextEdge;
		}
	}
	
	FreeQueue(q);
	return 1;	
}

	
/* FUNCIONES DEL CONTRATO */

digraphADT
NewDiGraph(CmpNodesFn cmpFn, int NodeSize, int EdgeSize)
{
	digraphADT aux;
	
	if (cmpFn == NULL)
	{
		fprintf(stderr, "NewGraph: One of the call back functions is missing \n");
		return NULL;
	}
	
	if (NodeSize <= 0 || EdgeSize <= 0)
	{
		fprintf(stderr, "NewGraph: Either the size of the info to be stored in the nodes or the edges are invalid \n");
		return NULL;
	}
	
	if ( (aux = calloc(1, sizeof(struct digraphCDT))) == NULL )
	{
		fprintf(stderr, "NewGraph: Not enought memory to create the graph\n");
		return NULL;
	}
	
	aux -> nsize = NodeSize;
	aux -> esize = EdgeSize;
	aux -> cmpFn = cmpFn;
	aux -> queue = NULL;
	aux -> actual = NULL;
	return aux;
}

int
DiGraphIsEmpty(digraphADT digraph)
{
	if (digraph == NULL)
		return -1;
	
	return digraph -> NodeCount == 0;
}

int
CreateNode(digraphADT digraph, nodeT info)
{
	nodeADT ant, rec, aux = NULL;
	
	if (digraph == NULL || info == NULL)
	{
		fprintf(stderr, "CreateNode: Invalid node data or graph \n");
		return 0;
	}
	
	ant = rec = digraph -> nodes;
	
	while (rec != NULL && digraph -> cmpFn(rec -> info, info) < 0)
	{
		ant = rec;
		rec = rec -> next;
	}
	
	/* Si el elemento ya existe, lo reemplazo por uno con el nuevo valor */
	
	if (rec != NULL && digraph -> cmpFn(rec -> info, info) == 0)
	{
		if (memcpy(rec -> info, info, digraph -> nsize) == NULL)  /* sobreescribe el dato */
		{
			fprintf(stderr, "CreateNode: The node already exist, node data overwrite was unsuccesful \n");
			return 0;
		}

		return 1;
	}
	
	/* si no lo crea */
	
	if ( (aux = calloc(1, sizeof(struct nodeCDT))) == NULL )
	{
		fprintf(stderr, "CreateNode: Not Enought memory to create node \n");
		return 0;
	}
	
	aux -> next = rec; /* aux -> info < rec -> info => aux -> next = rec :) */
		
	if ( (aux -> info = malloc(digraph -> nsize)) == NULL)
	{
		fprintf(stderr, "CreateNode: Not enought memory to insert data to node \n");
		free(aux);
		return 0;
	}
	
	if (memcpy(aux -> info, info, digraph -> nsize) == NULL)
	{
		fprintf(stderr, "CreateNode: Impossible to write info to node \n");
		free(aux -> info);
		free(aux);
		return 0;
	}
	
	if (ant == rec) /* es el primer nodo que se creo */
		digraph -> nodes = aux;
	else
		ant -> next = aux;
	digraph -> NodeCount++;
	
	return 1;
}

int 
NodeBelongs(digraphADT digraph, nodeT info)
{
	if (digraph == NULL || info == NULL)
	{
		fprintf(stderr, "NodeBelongs: graph or node data invalid \n");
		return -1;
	}
	
	return (SearchNode(digraph, info) != NULL);
}

int 
NodeCount(digraphADT digraph)
{
	if (digraph == NULL)
	{
		fprintf(stderr, "CantNodes: invalid graph \n");
		return -1;
	}
	
	return digraph -> NodeCount;
}

int 
InputEdges(digraphADT digraph, nodeT node)
{
	nodeADT aux;
	
	if (digraph == NULL || node == NULL)
	{
		fprintf(stderr, "InputEdges: invalid arguments to function InputEdges\n");
		return -1;
	}
	
	if ( (aux = SearchNode(digraph, node)) == NULL)
	{
		fprintf(stderr, "InputEdges: Node does not exist \n");
		return -1;
	}
	
	return (aux -> iedges);
}
		
	

int 
OutputEdges(digraphADT digraph, nodeT info)
{
	nodeADT naux;
	edgeADT eaux;
	int output = 0;
	
	if (digraph == NULL || info == NULL)
	{
		fprintf(stderr, "OutputEdges: invalud arguments to function OutputEdges \n");
		return -1;
	}
	
	if ( (naux = SearchNode(digraph, info)) == NULL)
	{
		fprintf(stderr, "OutputEdges: node does not belong to the graph \n");
		return -1;
	}
	
	eaux = naux -> adyac;
	
	while (eaux != NULL)
	{
		output++;
		eaux = eaux ->  nextEdge;
	}
	
	return output;
}

int
DeleteNode(digraphADT digraph, nodeT info)
{
	nodeADT prev, rec, nodeB;
	
	if (digraph == NULL || info == NULL)
	{
		fprintf(stderr, "DeleteNode: digraph or node are empty \n");
		return 0;
	}
	
	if ( (nodeB = SearchNode(digraph, info)) == NULL )
	{
		fprintf(stderr, "DeleteNode: Node does not exist \n");
		return 0;
	}
	prev = rec = digraph -> nodes;
	
	while (rec != NULL)
	{
		if (rec != nodeB)
			DeleteEdge(digraph, rec -> info, info); /* Busca y borra en la lista de adyacencias el nodo a borrar */
		if (rec -> next == nodeB)
			prev = rec;				/* almacena el nodo anterior al nodo a borrar en la lista de nodos */
		rec = rec -> next;
	}
	
	if (digraph -> nodes == nodeB)
		digraph -> nodes = nodeB -> next; /* si el nodo que se borra es el primero, ahora el primero es el contiguo */
	else
		prev -> next = nodeB -> next;
	
	FreeNode(digraph, nodeB);
	digraph -> NodeCount--;
	return 1;
}

int
CreateEdge(digraphADT digraph, nodeT src, nodeT tgt, edgeT edgeElement)
{
	int errorType1;
	nodeADT nodeSrc, nodeTgt;
	
	if (digraph == NULL || src == NULL || tgt == NULL || edgeElement == NULL)
	{
		fprintf(stderr, "CreateEdge: digraph, nodes or edge data are invalid \n");
		return 0;
	}
	
	if (digraph -> cmpFn(src, tgt) == 0)
	{
		fprintf(stderr, "CreateEdge: src and tgt nodes are the same, operation not allowed \n");
		return 0;
	}
	
	/* Si no existen los nodos, los crea */
	
	if ( (errorType1 = (CreateNode(digraph, src) == 0)) || (CreateNode(digraph, tgt) == 0) )
	{
		/* Si entra aca, alguno de los nodos no pudo ser creado */
		fprintf(stderr, "CreateEdge: Unable to create %s Node \n", errorType1 == 1 ? "Source" : "Target");
		
		if (!errorType1)
			FreeNode(digraph, src); /* si se creo el primero, pero el segundo fallo, libero el primero */
		
		return 0;
	}
	
	if ( IsConnected(digraph, tgt, src) )
	{
		fprintf(stderr, "CreateEdge: Impossible to create edge, tgt -> src edge already exist \n");
		return 0;
	}
	
	nodeSrc = SearchNode(digraph, src);
	nodeTgt = SearchNode(digraph, tgt);
	
	if (!InsertEdge(digraph, nodeSrc, nodeTgt, edgeElement))
	{
		fprintf(stderr, "CreateEdge: Unable to create edge between src and tgt nodes \n");
		return 0;
	}
	
	nodeTgt -> iedges++;
	
	return 1;
}

int
GetEdge(digraphADT digraph, nodeT src, nodeT tgt, edgeT * edgeElement)
{
	nodeADT nodeB;
	edgeADT curr;
	
	if (digraph == NULL || src == NULL || tgt == NULL || edgeElement == NULL)
	{
		fprintf(stderr, "GetEdge: Invalid arguments tso function GetEdge \n");
		*edgeElement = NULL;
		return 0;
	}
	
	if ( (nodeB = SearchNode(digraph, src)) == NULL )
	{
		fprintf(stderr, "GetEdge: Source Node is not in the digraph \n");
		*edgeElement = NULL;
		return 0;
	}

	curr = nodeB -> adyac;
	
	/* Busca en la lista de adyacencias del nodo "src", al nodo "tgt" */
	
	while (curr != NULL && digraph -> cmpFn(curr -> adyac -> info, tgt) < 0)
	{
		curr = curr -> nextEdge;
	}

	/* Si no lo encuentra retorna error */

	if (curr == NULL || digraph -> cmpFn(curr -> adyac -> info, tgt) != 0)
	{
		fprintf(stderr, "GetEdge: Target Node is not in the digraph \n");
		*edgeElement = NULL;
		return 0;
	}
	/* si no, extrae la información del arco que los une y la devuelve */
	
	*edgeElement = curr -> info;
	
	/* si no, extrae la información del arco que los une y la devuelve */
	
	/*
	if (memcpy(*edgeElement, curr -> info, digraph -> esize) == NULL)
	{
		fprintf(stderr, "GetEdge: Impossible to copy edge information, was memory reserved for edgeElement? \n");
		*edgeElement = NULL;
		return 0;
	}
	*/
	
	return 1;
}

int 
SetIteratorEdge(digraphADT digraph, nodeT src)
{
	nodeADT aux;
	edgeADT eaux;
	
	if (digraph == NULL || src == NULL)
	{
		fprintf(stderr, "SetIteratorEdge: invalid arguments to function SetIteratorEdge \n");
		return 0;
	}
	
	if ( (aux = SearchNode(digraph, src)) == NULL )
	{
		fprintf(stderr, "SetIteratorEdge: src node does not belong to the digraph \n");
		return 0;
	}
	
	eaux = aux -> adyac;
	aux -> actual = eaux;
	
	return 1;
}

int 
GetNextEdge(digraphADT digraph, nodeT src, edgeT * aim, nodeT * node)
{
	nodeADT aux;
	edgeADT eaux;
	
	if (digraph == NULL || src == NULL || aim == NULL || node == NULL)
	{
		fprintf(stderr, "GetNextEdge: invalid arguments to function GetNextEdge \n");
		return -1;
	}
	
	if ( (aux = SearchNode(digraph, src)) == NULL )
	{
		fprintf(stderr, "GetNextEdge: node src does not belong to the graph \n");
		return -1;
	}
	
	eaux = aux -> actual;
	
	if (eaux != NULL)
	{
		*aim =  eaux -> info;
		*node = eaux -> adyac -> info;
		/*
		if (memcpy(aim, eaux -> info, digraph -> esize) == NULL)
		{
			fprintf(stderr, "GetNextEdge: Unable to retrieve next edge \n");
			return -1;
		}
		
		if (memcpy(node, eaux -> adyac -> info, digraph -> nsize) == NULL)
		{
			fprintf(stderr, "GetNextEdge: Unable to retrieve node at which Edge is connected \n");
			return -1;
		}
		*/
		aux -> actual = eaux -> nextEdge;
	}
	else
		return 0;
	
	return 1;
}

int
DeleteEdge(digraphADT digraph, nodeT src, nodeT tgt)
{
	nodeADT nodeSrc, nodeTgt;
	edgeADT prev, rec;
	
	if ( (nodeSrc = SearchNode(digraph, src)) == NULL )
		return 0;
	
	if ( (nodeTgt = SearchNode(digraph, tgt)) == NULL )
		return 0;
	
	prev = rec = nodeSrc -> adyac;

	while (rec != NULL && digraph -> cmpFn(rec -> adyac -> info, tgt) < 0)
	{
		prev = rec;
		rec = rec -> nextEdge;
	}
	
	if (rec == NULL || (digraph -> cmpFn(rec -> adyac -> info, tgt) > 0) )
		return 0; /* Retorna indicando que la arista a borrar no existe */
	
	/* Si llego aca encontro el nodo a borrar en la lista de adyacencias del nodo actual */
	
	if (prev == rec) /* si en la lista de adyacencias, el nodo a borrar es el primero ...*/
		nodeSrc -> adyac = rec -> nextEdge;
	else
		prev -> nextEdge = rec -> nextEdge;
	
	FreeEdge(digraph, rec);
	digraph -> EdgeCount--;
	
	nodeTgt -> iedges--; /* decremento la cantidad de aristas que llegan a este nodo */
	
	return 1;
}

int 
EdgeCount(digraphADT digraph)
{
	if (digraph == NULL)
	{
		fprintf(stderr, "EdgeCount: Invalid argument to function EdgeCount \n");
		return 0;
	}
	
	return digraph -> EdgeCount;
}

int 
IsConnected(digraphADT digraph, nodeT src, nodeT tgt)
{
	nodeADT nodeSrc;
	edgeADT curr;
	int connected = 1;
	
	if ((nodeSrc = SearchNode(digraph, src)) == NULL)
	{
		fprintf(stderr, "IsConnected: source node does not exist on the digraph \n");
		return 0;
	}
	
	curr = nodeSrc -> adyac;
	
	while (curr != NULL && digraph -> cmpFn(tgt, curr -> adyac -> info) > 0)
		curr = curr -> nextEdge;
		
	if (curr == NULL || digraph -> cmpFn(tgt, curr -> adyac -> info) != 0)
		connected = 0;
		
	return connected;
}

int 
SetIteratorBFS(digraphADT digraph, nodeT start)
{
	nodeADT begin;
	
	if (digraph == NULL || start == NULL)
	{
		fprintf(stderr, "SetIteratorBFS: invalid arguments to function SetIteratorBFS \n");
		return 0;
	}
	
	if (digraph -> NodeCount == 0)
	{
		fprintf(stderr, "SetIteratorBFS: No nodes in the digraph, can't initialize iterator \n");
		return 0;
	}
	
	if (digraph -> queue != NULL) /* si ya existe una cola creada de alguna iteracion previa, la elimina */
	{
		FreeQueue(digraph -> queue);
		digraph -> queue = NULL;
	}
	
	if ( ( digraph -> queue = NewQueue()) == NULL )
	{
		fprintf(stderr, "SetIteratorBFS: Not enought memory to initialize iterator \n");
		return 0;
	}
	
	if ( (begin = SearchNode(digraph, start)) == NULL )
	{
		fprintf(stderr, "SetIteratorBFS: The node where the iteration should start does not exist \n");
		return 0;
	}
	
	/* PathBFS deja en la cola del header del digrafo, los elementos de los nodos ordenados al recorrerlo desde
	 * "start" con BFS
	 */ 
	
	PathBFS(digraph, begin);  
	
	return 1;
}

nodeT 
GetNextNodeBFS(digraphADT digraph)
{
	nodeT aux;
	
	if (digraph == NULL)
	{
		fprintf(stderr, "GetNextNodeBFS: invalid arguments to function GetNextNodeBFS \n");
		return NULL;
	}
	if ( digraph->queue != NULL && !QueueIsEmpty(digraph -> queue))
		aux = Dequeue(digraph -> queue);
	else
	{
		FreeQueue(digraph -> queue);	/* si la cola esta vacía, se termino de iterar, se la libera */
		digraph -> queue = NULL;		/* Indica que en la próxima iteración hay que crear una nueva cola */
		aux = NULL;
	}

	return aux;
}
	

void 
FreeDiGraph(digraphADT digraph)
{
	FreeForAll(digraph, digraph -> nodes);
	if (digraph -> queue != NULL)
		FreeQueue(digraph -> queue);
	free(digraph);
	return;
}




/*
 * Funciones setbegin y getdato para iterar por el grafo
 */
 
void
SetBeginDiGraph( digraphADT digraph )
{
	digraph->actual = digraph->nodes;
}

nodeT
GetNextNode( digraphADT digraph )
{
	nodeT nodo;
	
	if( digraph->actual == NULL)
		return NULL;
	nodo = digraph->actual->info;
	digraph->actual = digraph->actual->next;

	return nodo;
}

int
IsLastNode( digraphADT digraph, nodeT node )
{
	nodeADT nodo;
	
	nodo = SearchNode( digraph, node);
	if( nodo->next == NULL)
		return 1;
	else
		return 0;
}


